package algorithm_demo.sort;

import java.util.Arrays;

/**
 * 归并排序
 * <p>
 * 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法 (Divide and Conquer) 的一个非常典型的应用。
 * 归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2 - 路归并。
 * 和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间
 * <p>
 * 算法步骤
 * 归并排序算法是一个递归过程，边界条件为当输入序列仅有一个元素时，直接返回，具体过程如下：
 * 1. 如果输入内只有一个元素，则直接返回，否则将长度为 n 的输入序列分成两个长度为 n/2 的子序列；
 * 2. 分别对这两个子序列进行归并排序，使子序列变为有序状态；
 * 3. 设定两个指针，分别指向两个已经排序子序列的起始位置；
 * 4. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间（用于存放排序结果），并移动指针到下一位置；
 * 5. 重复步骤 3 ~4 直到某一指针达到序列尾；
 * 6. 将另一序列剩下的所有元素直接复制到合并序列尾。
 * <p>
 * 算法分析
 * 稳定性：稳定
 * 时间复杂度 ：最佳：O(nlogn)， 最差：O(nlogn)， 平均：O(nlogn)
 * 空间复杂度 ：O(n)
 *
 * @author Api
 * @date 2022/11/19 12:06
 */
public class MergeSort2 {

    public static void main(String[] args) {
        int[] arr = new int[]{2, 34, 45, 56, 2, 1, 34, 5, 5, 3, 2, 1, 34, 5};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    //左神
    public static void mergeSort(int[] arr, int L, int R) {
        if (L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        mergeSort(arr, L, mid);
        mergeSort(arr, mid + 1, R);
        merge(arr, L, mid, R);
    }


    public static void merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        //两个都不越界
        while (p1 <= M && p2 <= R) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        //以下两个while只会中一个，主要考虑到是否L和R谁先会越界的问题，将剩余的数copy到剩余的空间中
        while (p1 <= M) {
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        //这个merge后的结果，然后将这个结果copy到原数组
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
    }
}
